The invention relates to data communication networks and, in particular, to methods and apparatus for accessing data networks.
Numerous computer networking schemes have been employed for some time, with varied success. For example, a carrier send multiple access/collision detection (CSMA/CD) network such as the Ethernet sends messages and packets with a preamble and error checking. To gain access to the network, a sender waits until there is no activity on the network, begins to send the message and at the same time checks for interference. As long as there is no interference the sender continues to send the message. However, if the sender detects interference, the sender jams the network, aborts its transmission and waits a random amount of time before re-sending. Each Ethernet message is organized into packets which include a header that identifies the recipient and sender, a preamble indicating the packet""s length, type and sequence number, followed by the actual data, and, finally, a cyclical redundancy check sum (CRC) which the recipient can employ to verify error-free operation. Repeated collisions and retries associated with heavy traffic on an Ethernet network may lead to substantial delays in the delivery of messages.
A token ring network employs a closed set of nodes organized in a ring topology. A device connected to the ring may send along the network only if it has possession of the token. The token is typically a short message that is passed around a ring until a device that wishes to transmit extracts the token from the ring. When the sender is finished sending its message, which may be many packets long, the sender releases the token and sends it around the ring. Then another device which needs to send data along the ring may acquire the token and commence sending. Unfortunately, a node may hold the token for an extended period of time, thereby blocking access to the network.
More recently, alternative networks have been developed which are based on protocols such as the IEEE xe2x80x9cserial expressxe2x80x9d standard. P2100, Draft 0.781 of the standard is hereby incorporated by reference and may be obtained from the IEEE at the following address: IEEE Standards Department Copyright and Permissions 445 Hoes Lane, P.O. Box 1331, Piscataway, N.J. 08855-1331. Serial Express specifies a high speed interconnect design for use with high speed device, including video cameras, monitors, serial bus bridges, PCI-card chassis, high performance I/O devices, and for low cost group clustering. Serial express employs low cost serial link technology that can operate at rates of 1 gigabit per second, provides for variable length data packets, and permits bidirectional operation. Such high data rates provide high bandwidth, low latency access to workstation/personal computer memory systems and high bandwidth input/output for high performance disk subsystems, for example.
Access to such a network should be simple, efficient and fair. An arbitration system that provides access to the network should be simple in order to avoid implementation errors and to avoid complex testing procedures. In order to provide the maximum benefit of the network system, an arbitration mechanism should be efficient. That is, gaining access to the network should not require a complex series of steps that consume a great deal of time, thereby reducing the throughput of the network. The arbitration mechanism should also allow every device connected to the network to access the network. That is, no device connected to the network should be permitted to dominate the network by continually sending and thus preventing other devices connected to the network from obtaining access. There is a need, therefore, for network access devices and methods which provide simple, efficient and fair access to such a network.
In accordance with the principles of the invention, each network interface unit, or network adapter, connected to the network includes a bypass buffer, generally organized as a first in first out (FIFO), which buffers packets that pass through the network and are directed to downstream adapters. In order to provide fair, efficient access to the network for every device connected to the network through a network adapter, each network adapter operates in one of four modes: as a xe2x80x9csenderxe2x80x9d, a xe2x80x9cfused bypass headxe2x80x9d, a xe2x80x9cdonorxe2x80x9d, or a xe2x80x9cfused bypass memberxe2x80x9d. The adapter""s operating mode depends upon whether the adapter has packets to send from the device which the adapter connects to the network, upon whether another adapter has requested that the adapter suspend its transmission of packets, and upon whether the adapter has sufficient room within its bypass buffer.
Each adapter has the ability to request a pause in transmission from its upstream neighboring network adapter. If an adapter has received such a pause request, the adapter may operate as a donor, as a member, or as a head. If an adapter has not received a pause request, it may operate as a sender or as a head.
Whenever an adapter is to transmit a local packet, i.e., a packet generated by the device which the adapter connects to the network, onto the network, and the adapter has not received a pause request, the adapter may operate as a sender. As a sender, the adapter first examines its bypass buffer and, if there is sufficient room in its bypass buffer to ensure that no overflows will occur, the adapter transmits its local packet onto the network. That is, the adapter will transmit the local packet if there is room available within its bypass buffer to store whatever bypass packets may arrive during the time the local packet is being transmitted. In an illustrative embodiment the adapter includes a bypass buffer that is at least twice as xe2x80x9clongxe2x80x9d as the longest packet supported by the network. Since bypass packets arrive at the same rate that local packets are sent, the bypass buffer will not overflow so long as the local packet to be sent would fit within the space available within the bypass buffer. Consequently, in an illustrative embodiment, an adapter acting as a sender transmits a local packet if there is enough room available within the adapter""s bypass buffer to store a packet as long as the local packet.
If there is not enough room within the adapter""s bypass buffer to permit the transmission of a local packet, the adapter attempts to limit the number of packets being transmitted to it by sending a request to its nearest upstream neighboring adapter, that is, to the adapter from which it most directly receives packets, to suspend the transmission of packets. In response to this request for, or assertion of, xe2x80x9cpausexe2x80x9d, the upstream adapter will suspend the transmission of data packets as soon as it completes the transmission of any packet it may be in the process of sending if the upstream adapter is able to suspend its transmission of packets. Instead of transmitting data packets, the upstream adapter will send xe2x80x9cIDLExe2x80x9d packets, i.e., relatively short packets that contain status information. An IDLE packet is discarded by an adapter which receives one. While receiving IDLE packets, the downstream adapter continues to transmit one or more data packets from its bypass buffer, thereby xe2x80x9cdrainingxe2x80x9d its bypass buffer. When the downstream adapter""s bypass buffer is emptied, the downstream adapter sends a local packet and de-asserts the pause request it had made to its upstream neighbor.
In some circumstances an upstream adapter should not pause in response to a pause request. For example, if the upstream adapter""s own bypass buffer is full, it would run the risk of overflowing its own bypass buffer if it stopped transmitting packets from its bypass buffer and transmitted IDLE packets to its downstream, pauserequesting, neighbor. In such a case, the upstream adapter asserts pause to its own upstream neighbor which suspends the transmission of data packets and transmits IDLE packets in response, if its own bypass buffer is not full. The intermediate adapter continues to transmit data packets from its own bypass buffer until it""s bypass buffer is empty. The process may be repeated until an upstream adapter is reached which can send IDLE packets. In this manner a chain of adapters is formed, all of which are asserting pause to their upstream neighbors in a chain. The bypass buffers, or FIFOs, appear to be fused together. The intermediate adapter empties its bypass buffer, then sends IDLE packets to the original pause-requesting adapter, thus permitting that adapter to empty its bypass buffer, send its local data packet and de-assert its pause request. Subsequently, the upstream adapters may de-assert their pause requests.
The original pause-requesting adapter in the thus-formed chain of adapters will be referred to hereinafter as the xe2x80x9cheadxe2x80x9d of a xe2x80x9cfused bypassxe2x80x9d. An intermediate adapter, one which is unable to suspend its transmission of bypass packets in response to a request for a pause by a fused bypass head and which itself requests a pause from its upstream neighbor, will be referred to as a fused bypass xe2x80x9cmemberxe2x80x9d. An adapter which suspends its transmission of all packets other than IDLE packets in response to a request for a pause from a downstream packet will be referred to, generally, as a xe2x80x9cdonorxe2x80x9d. If the donor adapter is the last adapter in the fused bypass it is referred to as the xe2x80x9ctailxe2x80x9d of the fused bypass. A plurality of fused bypasses may form within the network at any given time and the tail of a given fused bypass may extend upstream from an existing fused bypass by the addition to the fused bypass of network adapters.
In an illustrative embodiment, a network adapter in accordance with the principles of the invention includes two sets of unidirectional, input and output ports, control logic, and a bypass buffer. The input and output ports for one direction of data transmission are employed, primarily, to send/receive data and the input and output ports for the other direction are employed, primarily, to send/receive network access arbitration information. In an associated network, data is transmitted around the network in one direction along one ring and arbitration, or control/status, information is transmitted around the network in the opposite direction around the other ring.
From the perspective of the data input port, the control logic examines packets received at the data input port and strips the packet from the data stream if the packet is directed to the particular network adapter or it""s associated device. If the packet is not directed to the particular adapter, the packet is placed in the bypass buffer, which is, illustratively, at least twice the length of the largest packet permitted on the network.
From the perspective of the data output port, the control logic controls access to the network through the data output port by routing packets from either the bypass buffer or from the device attached to the network through the network adapter. IDLE packets, that is, short packets containing no data, are also routed to the data output port and may be generated, illustratively, by the control logic. If an adapter has a local packet to send, that is, if the adapter has a packet generated by the device which the adapter connects to the network to send, the adapter examines its bypass buffer and only sends the local packet if there is sufficient room in its bypass buffer to insure that no bypass packets will be dropped.